#include <iostream>
#include <vector>
#include <stack>
#include <ctime>

int getRandom(std::vector<int> &nums, int left, int right)
{
    int r = rand() % (right - left);
    return nums[left + r];
}

// 递归实现
void quick_sort1(std::vector<int> &nums, int l, int r)
{
    if (l >= r)
        return;

    int key = getRandom(nums, l, r);
    int left = l - 1, right = r + 1, i = l;
    while (i < right)
    {
        if (nums[i] < key)
            std::swap(nums[++left], nums[i++]);
        else if (key == nums[i])
            i++;
        else
            std::swap(nums[--right], nums[i]);
    }

    // [l,left] [left + 1,right - 1] [right,r]
    quick_sort1(nums, l, left);
    quick_sort1(nums, right, r);
}

// 非递归实现
void quick_sort2(std::vector<int> &nums)
{
    std::stack<int> st;
    st.push(nums.size() - 1);
    st.push(0);

    while (st.size())
    {
        int l = st.top();
        st.pop();
        int r = st.top();
        st.pop();
        if (l >= r)
            continue;
        int key = getRandom(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (nums[i] < key)
                std::swap(nums[++left], nums[i++]);
            else if (key == nums[i])
                i++;
            else
                std::swap(nums[--right], nums[i]);
        }
        // [l,left] [left + 1,right - 1] [right,r]
        st.push(left);
        st.push(l);
        st.push(r);
        st.push(right);
    }
}

int main()
{
    srand(time(nullptr));
    std::vector<int> nums = {10, 2, 3, 5, 4, 8, 7, 6, 8, 9, 1};
    quick_sort1(nums, 0, nums.size() - 1);
    quick_sort2(nums);
    for (auto x : nums)
    {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}